package 递归or回溯;
import java.util.*;
/**
 * 生成所有有效的括号组合
 * 时间复杂度O(2^n)，空间复杂度O(n)，n为括号对数
 */
public class generateParenthesis {
    /**
     * 生成所有有效的括号组合
     * 
     * @param n 括号对数
     * @return 所有有效的括号组合列表
     */
    public static List<String> generateParenthesisM(int n){
        back(n, n, ""); // 调用回溯方法生成括号组合
        return list; // 返回生成的括号组合列表
    }

    static List<String> list = new ArrayList<>(); // 用于存储生成的括号组合

    /**
     * 回溯方法，用于生成括号组合
     * 
     * @param left 剩余左括号数量
     * @param right 剩余右括号数量
     * @param cur 当前生成的括号组合
     */
    public static void back(int left, int right, String cur){
        if(left == 0 && right == 0){ // 如果左右括号都用完，表示生成了一个有效的括号组合
            list.add(cur); // 将当前组合加入结果列表
            return; // 返回
        }
        if(left > right) return; // 如果剩余左括号数量大于右括号数量，表示当前组合无效，返回
        // 例如，对于组合 "())"，左括号数量为1，右括号数量为2，此时 left < right，表示这个组合是无效的
        // 因为右括号数量过多，无法形成有效的括号组合
        if(left > 0) back(left - 1, right, cur + "("); // 如果还有左括号，递归生成左括号
        if(right > 0) back(left, right - 1, cur + ")"); // 如果还有右括号，递归生成右括号
    }

    /**
     * 主函数：处理输入输出
     * 输入格式：一个整数n，表示括号对数
     * 输出格式：所有有效的括号组合列表
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 读取括号对数
        System.out.println(generateParenthesisM(n)); // 输出生成的括号组合
        sc.close(); // 关闭输入流
    }
}
